package homework1_array.alg_106;

import static homework1_array.Utils.printList;

public class ArrayHomework {

    public static void main(String[] args) {

        //todo 作业1：完成这个测试方法中的addByElementBySequence()方法
        arrayAddTest();

        // todo 作业2：完成这个测试类中的removeByElement()方法
        deleteTest();

    }

    /**
     * 在有序列表中插入元素
     */
    private static void arrayAddTest() {

        int[] arr = new int[20];
        arr[0] = 3;
        arr[1] = 4;
        arr[2] = 7;
        arr[3] = 8;
// 1.中间位置插入
        addByElementSequence(arr, 4, 6);
        printList("在有序数组的中间部分插入元素后的结果为：", arr, 5);
        //此时应输出 3 4 6 7 8

//2.尾部插入
        addByElementSequence(arr, 5, 9);
        printList("在有序数组的尾部插入元素后的结果为：", arr, 6);
        //此时应输出 3 4 6 7 8 9

//3.数组首部插入
        addByElementSequence(arr, 6, 1);
        printList("在有序数组的首部部分插入元素后的结果为：", arr, 7);
        //此时应输出：1 3 4 6 7 8 9

    }

    //todo 作业1：完成这个方法

    /**从后往前，一边移动，一边比对，找到要插入的位置
     * @param arr     存储元素的数组
     * @param size    数组中已经存储的元素数量
     * @param element 要插入数组的新元素
     * @return
     */
    public static void addByElementSequence(int[] arr, int size, int element) {
        int index = 0; // 默认源数组中的所有元素都比给定的元素大，则给定的元素就要插入 在 第一个位置
        for(int i = size -1; i >=0 ;i -- ){
            if(arr[i] > element){//遍历到的位置的元素比给定元素大，直接将当前位置的元素复制给下一个位置
                arr[i+1] = arr[i];
            }else{
                index = i +1; // 第一个比给定元素小的位置，给定元素需要插入的位置就是 这个位置 + 1,并跳出遍历
                break;
            }
        }
        arr[index] = element;
    }

    /**先遍历数组找到应该插入的位置，再从后往前移动元素，插入给定的元素
     * @param arr     存储元素的数组
     * @param size    数组中已经存储的元素数量
     * @param element 要插入数组的新元素
     * @return
     */
    public static void addByElementSequence_1(int[] arr, int size, int element) {
        int index = size;//默认所有的元素都比给定的元素小，那么给定的元素就要插入到 index  = size  的位置
        for(int i = 0;i<size;i++){
            if(arr[i] > element){ // 找到 第一个比 给定元素大的元素，并记录该元素的位置，这个位置就是给定元素需要插入的位置
                index = i;
                break;
            }
        }
        for(int i = size -1 ;i>=index; i--){//从后开始一次移动移动元素，直到给定元素插入的位置位置,原来在 idnex 位置上的元素，也要往后移动(所以 i>=index)
            arr[i+1] = arr[i];
        }

        arr[index] = element;
    }


    /**
     * 删除测试
     */
    private static void deleteTest() {
        int[] arr = new int[]{2, 3, 4, 9, 10, 11, 12};

//1.删除头元素
        removeByElement(arr, 7, 2);
        printList("删除头元素后的结果为：", arr, 6);
        //此时应该打印 3 4 9 10 11 12

//2. 删除尾元素
        removeByElement(arr, 6, 12);
        printList("删除尾元素的结果为：", arr, 5);
        //此时应该打印 3 4 9 10 11

//3. 删除中间元素：
        removeByElement(arr, 5, 9);
        printList("删除中间元素的结果为：", arr, 4);
        //此时应该打印 3 4 10 11
    }
    /**
     * 从数组中删除元素
     * @param arr
     * @param size 数组已经存放的元素大小
     * @param key  要删除的元素
     */
    public static void removeByElement(int[] arr, int size, int key) {
        int index =  -1;
        for(int i = 0; i<size; i++){
            if(arr[i]== key){
                index = i;//找到等于给定元素的位置,,并跳出遍历
                break;
            }
        }
        if(index < 0){ // 如果未查询到等于给定的元素
            return ;
        }
        //从找到的位置开始往后遍历，将每一个元素往前移动
        for(int i=index; i<size-1 ;i++){
            arr[i] = arr[i+1];
        }

    }
}
